The implementation of an integrated circuit (IC) begins with a programmatic representation of the hardware embedded in it. The programmatic representation is nominally created using a Hardware Description Language (HDL), for example System Verilog or VHDL. The programmatic description is systematically refined to a level of detail from which the IC can be manufactured using a semiconductor foundry manufacturing process.
Two intermediate representation levels that are nominally adjacent to each other are the Register Transfer Level (RTL) and the Gate Level. Both are representations of the logic circuits and state-holding elements implementing the hardware. Whereas the RTL representation is nominally in terms of technology-independent logic expressions and software-program-like constructs, the gate-level representation (also called the gate-level netlist) is nominally a logic circuit representation in terms of a library of logic cells implementing combinational gates (e.g. AND, XOR, OR gates), storage elements (e.g. flip-flops, latches) and connecting wires (also called “nets”). The nets could serve as inputs into the netlist, as outputs of the netlist, or as interconnections between logic gates, storage elements or a mix thereof. The “cell library” is nominally developed in collaboration with the manufacturing foundry and is characterized for area, delay, power etc as part of that process. A gate-level netlist is typically produced automatically from an RTL representation by the process of “synthesis” by using a “synthesis tool” software program. The typical design flow is shown in FIG. 1.
Gate-level simulation is the process of simulating the effect of input stimuli applied to the gate-level netlist. A combination of RTL versus gate-level formal equivalence checking, and gate-level simulation is used for functionally validating the gate-level netlist. This is also shown in FIG. 1. Emulation or hardware-accelerated simulation is nominally the same as simulation using a “software simulator”, with the difference that the model of the design being simulated is implemented on special-purpose hardware intended to speed up the simulation. Gate-level netlist validation is nominally the final functional validation step before physical design. As a result, gate-level simulation is a very important step in the IC design process and must be enabled with minimum overhead and must be maximally efficient in terms of performance and its use of human and computer resources. The presence of X values on nets is a major impediment in the successful use and completion of gate-level simulation.
At any given time in gate-level simulation, some of the nets may have unknown values. For example, an input net might not have a value specified, a storage element might be uninitialized, or the combined output of interacting internal logic elements like tristate buffers might be unresolved. When the value on a net in the actual hardware is unknown, it is still one of either 0 or 1. In other words, in the actual hardware the values on nets are binary. On the other hand, an unknown value on a net in gate-level simulation is represented as a symbol “X” distinct from 0 and 1. In fact, gate-level simulation also allows for additional symbols other than 0, 1 or X as net values, which do not need to be considered for the purpose of this disclosure without loss of generality. In effect, gate-level simulation models each logic and storage element as a multi-valued input-output function. For the purpose of the present invention, it is convenient and sufficient to model any value other than 0 or 1 effectively as an X.
The ternary simulation in the presence of 0, 1 and X on the nets of the gate-level simulation model deviates from the actual hardware in the determination of 0, 1 and unknown values on nets driven by logic elements when a logic element has X values on multiple of its inputs such that the unknown values represented by the X values on the different inputs are correlated to each other.
A simple example of such an occurrence would be an XOR gate with two inputs such that each input has an X value and the X values both originate at the same source. In the actual hardware, the two inputs of the XOR gate would either both be 1 or both be 0, and the output of the XOR gate in the actual hardware would be a 0 in either case. Gate-level simulation, on the other hand, is limited in that it is unable to track the correlations between the binary values underlying the two Xs and would, as a result, conclude only that the output of the XOR gate is also an X. This phenomenon is called X-pessimism since the simulator takes the safe (pessimistic) decision of propagating an X while the value in the actual hardware resolves to a binary 0 or 1. (FIG. 2)
Another common example is that of an AND-OR multiplexor logic element. A multiplexor propagates the value at one of a number of “data” inputs based on the value on its “select” input. Consider a multiplexor with two data inputs and a select input bit that chooses between the two data inputs, and specifically the case where the select input has the value X and the two data inputs are both at value 1. The output value of the multiplexor in the actual hardware would be a 1 regardless of the actual value on the select input, whereas gate-level simulation would compute an X value at the output as a result of X-pessimism. (FIG. 3). Similarly, an OR-AND multiplexor would incorrectly simulate an output value of X when the select input has the value X and the two data inputs have the value 0. In either implementation, if the two data values are different and the select input is at X, the simulated X value is correct. In other words, it is not pessimistic and does not need correction.
X-pessimism has been well known as a limitation of gate-level simulation since the first use of gate-level simulation. X-pessimism is also possible in RTL simulation, and the present invention can be applied to correct X-pessimism in RTL simulation as well.
It is common knowledge that X-pessimism can be avoided by augmenting the circuit implementation of a logic model or a collection of logic models. In the case of a two-input AND-OR multiplexor for instance, an augmentation in the form of an AND gate that has its inputs the two data inputs of the multiplexor, and whose output is ORed with the output of the original multiplexor to obtain the output of the augmented model would correctly compute the output value as 1 when the two data input values are 1 and the select input value is an X. In effect, the augmentation is a bypass path that “knows” when the gate-level simulation would be X-pessimistic and corrects it on the fly. Such augmentation can be done by adding gates to the netlist as shown here or by means of auxiliary code in the simulation testbench that effectively performs the same task. (FIG. 4)
Whereas the possibility of applying such augmentation in specific situations, for example for the aforementioned multiplexor, has been well known, applying such augmentation in the general case where it is desired to correct X-pessimism in situations where the functionality of the logic causing it is not known a priori has been a difficult problem to solve. Some methods have been proposed in this regard in the recent past that are summarized below.
Chang et al. published U.S. Pat. Nos. 9,058,452 and 8,402,405 in which a method was proposed wherein nets in the gate-level model were monitored for X values generated during gate-level simulation, and the X-generating trace was analyzed formally to determine if the X was genuine. If the X was found to be caused by X-pessimism, the correct value was forced on it using auxiliary code in the testbench. U.S. Pat. No. 8,402,405 applied this method for combinational logic cones driving the X value and U.S. Pat. No. 9,058,452 extended it to sequential logic cones. Among the disadvantages of this approach is that time-consuming formal analysis must be applied during simulation and for every X that is produced, causing significant simulation run time overhead. Also, the formal analysis is performed in the context of a specific trace, implying that it may need to be performed again for the same net when an X is produced on it by a different trace. The articles by Chang et al., “Improving Gate Level Simulation Accuracy when unknowns exist”, Jun. 3, 2012, ACM, pp. 1-5, and “Handling Nondeterminism in Logic Simulation So That Your Waveform Can Be Trusted Again”, D & T Early Access, Publisher: IEEE, Published in: US Mar. 7, 2013, propose similar methods that pivot on generated X values and the corresponding traces.
Salz et al. published U.S. Pat. No. 8,650,513 in which a method was proposed wherein the basic approach is to identify nets that fanout and subsequently reconverge at some logic element in the netlist. Either all nets or user-specified nets downstream from these reconvergent points are marked for X-pessimism analysis during gate-level simulation. The method creates an alternative model with two copies of the logic between the nets that fanout and the nets marked for X-pessimism analysis such that when an X is detected at the fanout points in gate-level simulation, a 0 value and a 1 value are propagated along the net in the two copies of the logic. If the value at the nets marked for X-pessimism analysis are the same in the two copies, the method concludes that the X is pessimistic and corrects it by forcing the value determined in the alternative model. This method has a number of limitations and drawbacks among which are that the determination of the candidates for which to perform this analysis is imprecise and relies on user input, the creation of the alternative model of the logic is burdensome to the simulator in terms of memory as well as performance overhead, and the fact that the method explicitly simulates 0 and 1 values along the alternative paths implies that it is not complete in its ability to handle situations where X values from multiple sources propagate along the logic to the X-pessimism points of interest.
The above two approaches are the closest in terms of attempting to correct X-pessimism on the fly. Various other publications address X-pessimism in gate-level simulation, but do not in any manner impinge on the present invention.